1881E - Block Sequence - CodeForces Solution

#include<bits/stdc++.h>
#define vc vector
#define lson l,mid,rt<<1
#define rson m+1,r,rt<<1|1
#define sall(a) sort(a.begin(),a.end())
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define range(x) begin(x),end(x)
#define stop system("pause");
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=2e5+10;
const ll inf=1e9;
const int mod=1e9+7;
int T,n,m,d,k;
void solve()
{
    cin>>n;
    vc<int>a(n+1),f(n+3);
    for(int i=1;i<=n;i++)   cin>>a[i];
    f[n]=1;
    for(int i=n-1;i>=1;i--){
        if(a[i]<=n-i){
            f[i]=min(f[i+1]+1,f[i+a[i]+1]);
        }else {
            f[i]=f[i+1]+1;
        }
    }
    cout<<f[1]<<endl;
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin>>T;
    while(T--)
    {
        solve();
    }
    stop
    return 0;
}